#![allow(unused)]

pub use debug::*;
pub use std::{
    borrow::*,
    cell::*,
    cmp::*,
    collections::*,
    fmt::*,
    ops::*,
    option::Option,
    rc::*,
    result::Result,
    sync::atomic::Ordering,
    sync::{atomic::*, mpsc::*, *},
    thread::*,
    time::*,
};

/// 数学函数相关
pub mod algorithm {
    use acm::Borrow;
    use std::borrow::BorrowMut;
    use std::cell::RefCell;
    /// 拓扑排序相关
    use std::collections::VecDeque;
    /// 并查集相关
    use std::convert::{TryFrom, TryInto};
    use std::mem::swap;
    use std::num::Wrapping;
    use std::ops::*;
    use std::rc::Rc;

    /// 根据`edges(边缘)`数组生成`dep(入度)`数组和`graph(邻接表)`
    pub fn generate_dep_graph(n: usize, edges: &[Vec<i32>]) -> (Vec<usize>, Vec<Vec<usize>>) {
        let mut dep = vec![0; n];
        let mut graph = vec![vec![]; n];
        for item in edges.iter() {
            graph[item[1] as usize].push(item[0] as usize);
            dep[item[0] as usize] += 1;
        }
        (dep, graph)
    }

    /// 根据`dep(入度)数组`、`graph(邻接表)`和`items(待排序对象数组)`生成拓扑顺序
    ///
    /// 该算法使用的是广度优先算法的拓扑排序，复杂度为`O(n)`
    pub fn top_sort(dep: &mut Vec<usize>, graph: &[Vec<usize>], items: &[usize]) -> Vec<usize> {
        let mut q = VecDeque::new();
        for item in items {
            if dep[*item] == 0 {
                q.push_back(*item);
            }
        }
        let mut res = vec![];
        while !q.is_empty() {
            let u = *q.front().unwrap();
            q.pop_front();
            res.push(u);
            for v in &graph[u] {
                dep[*v] -= 1;
                if dep[*v] == 0 {
                    q.push_back(*v);
                }
            }
        }
        if res.len() == items.len() {
            res
        } else {
            vec![]
        }
    }

    #[derive(Debug)]
    /// 并查集
    pub struct DSU {
        data: Vec<i32>,
    }

    impl DSU {
        /// 新建一个并查集，给入一个参数`i`，表示该并查集最大能容纳的元素数量，每个元素的初始集合都为自己
        ///
        /// 示例：
        /// ```rust
        /// let bcj = DSU::new(20);
        /// ```
        pub fn new<T>(i: T) -> Self
        where
            usize: TryFrom<T>,
        {
            DSU {
                data: vec![-1i32; usize::try_from(i).unwrap_or(usize::MAX)],
            }
        }
        /// 以数组方式展示全集
        pub fn show(&self) {
            println!("{:?}", self.data);
        }
        /// 合并两个元素所属的两个集合
        pub fn merge<T1, T2>(&mut self, x: T1, mut y: T2) -> bool
        where
            usize: TryFrom<T1>,
            usize: TryFrom<T2>,
        {
            let mut x = usize::try_from(x).unwrap_or(0);
            let mut y = usize::try_from(y).unwrap_or(0);
            x = self.root(x);
            y = self.root(y);
            if x != y {
                if self.data[y] < self.data[x] {
                    swap(&mut x, &mut y);
                }
                self.data[x] += self.data[y];
                self.data[y] = x as i32;
                true
            } else {
                false
            }
        }
        /// 返回该元素所属集合的根节点（一般无需使用）
        pub fn root(&mut self, x: usize) -> usize {
            if self.data[x] < 0 {
                x
            } else {
                self.data[x] = self.root(self.data[x] as usize) as i32;
                self.data[x] as usize
            }
        }
        /// 返回该元素所在集合中的元素数量
        pub fn size<T>(&mut self, x: T) -> usize
        where
            usize: TryFrom<T>,
        {
            let u = self.root(usize::try_from(x).unwrap_or(0));
            (-self.data[u]) as usize
        }
        pub fn same<T1, T2>(&mut self, x: T1, mut y: T2) -> bool
        where
            usize: TryFrom<T1>,
            usize: TryFrom<T2>,
        {
            self.root(usize::try_from(x).unwrap_or(0)) == self.root(usize::try_from(y).unwrap_or(0))
        }
    }

    type TrieTree = Rc<RefCell<TrieNode>>;

    struct TrieNode {
        next: Vec<Option<TrieTree>>,
        parent: Option<TrieTree>,
        is_end: bool,
    }

    impl TrieNode {
        fn new_node() -> TrieNode {
            TrieNode {
                next: vec![None; 26],
                parent: None,
                is_end: false,
            }
        }
        fn new() -> TrieTree {
            Rc::new(RefCell::new(TrieNode::new_node()))
        }
        fn insert(head: TrieTree, word: &str) {
            let mut h = head;
            for c in word.chars() {
                if h.as_ref().borrow().next[c as usize - 'a' as usize].is_none() {
                    let mut new = Rc::new(RefCell::new(TrieNode::new_node()));
                    h.as_ref().borrow_mut().next[c as usize - 'a' as usize] = Some(Rc::clone(&new));
                }
                let tmp = Rc::clone(
                    h.as_ref().borrow().next[c as usize - 'a' as usize]
                        .as_ref()
                        .unwrap(),
                );
                h = tmp;
            }
        }

        fn find_word(head: TrieTree, word: &str) -> bool {
            let mut h = head;
            for c in word.chars() {
                if h.as_ref().borrow().next[c as usize - 'a' as usize].is_none() {
                    return false;
                }
                let tmp = Rc::clone(
                    h.as_ref().borrow().next[c as usize - 'a' as usize]
                        .as_ref()
                        .unwrap(),
                );
                h = tmp;
            }
            true
        }
    }

    /// 马拉车算法
    pub mod manacher {
        pub fn expandstr(s: &str) -> String {
            let mut st = "$#".to_string();
            for ch in s.chars() {
                st.push(ch);
                st.push('#');
            }
            st
        }

        pub fn manacher_vec(s: &str) -> Vec<usize> {
            let se = expandstr(s).into_bytes();
            let n = se.len();
            let mut p = vec![0usize; n];
            let (mut mx, mut id) = (0, 0);
            for i in 1..n {
                p[i] = if mx > i { p[2 * id - i].min(mx - i) } else { 1 };
                while i + p[i] < n && se[i + p[i]] == se[i - p[i]] {
                    p[i] += 1;
                }
                if mx < i + p[i] {
                    mx = i + p[i];
                    id = i;
                }
            }
            // p.show();
            p.pop();
            p.remove(0);
            p.remove(0);
            for i in p.iter_mut() {
                *i -= 1;
            }
            p
        }
    }
}

/// debug相关
pub mod debug {
    use std::fmt::Debug;

    /// 为所有Debug对象实现.show()与.show_v()方法
    pub trait Tdebug<T = Self>: Debug {
        fn show_language(&self, language: &str, verbose: bool) {
            let mut val_str = format!("{:?}", self);
            let mut type_str = String::from(std::any::type_name::<T>());
            let l_str = match language {
                // 语言字符串
                "zh-cn" => ["变量调试信息", "调试信息结束", "内存地址", "类型", "值", "...内容过多,不方便打印！若要打印完整，请使用show_v()或将verbose参数设置为true"],
                _ => [
                    "Variable Information",
                    "Variable Information",
                    "position",
                    "type",
                    "val",
                    "...Too much to print! If you want to check the whole variable's value, please use show_v() or set the verbose to true",
                ],
            };
            if val_str.len() > 500 && !verbose {
                val_str.truncate(500);
                val_str.push_str(l_str[5]);
            }
            if verbose {
                println!("----------{}----------", l_str[0]);
                println!(
                    "{}: {:p}\n{}: {}\n{}: {}",
                    l_str[2], &self, l_str[3], type_str, l_str[4], val_str,
                );
                println!("----------{}----------", l_str[1]);
            } else {
                loop {
                    let mut tmp_str = String::new();
                    if let Some(r) = type_str.rfind(':') {
                        let (left, right) = type_str.split_at_mut(r + 1);
                        let mut i = left.len();
                        for ch in left.chars().rev().enumerate() {
                            if !(ch.1.is_alphabetic() || ch.1 == ':') {
                                i -= ch.0;
                                break;
                            }
                        }
                        if i != left.len() {
                            let (ll, _lr) = left.split_at_mut(i as usize);
                            tmp_str.push_str(ll);
                        }
                        tmp_str.push_str(right);
                    } else {
                        break;
                    }
                    type_str = tmp_str;
                }
                if val_str.len() <= 10 && type_str.len() <= 10 {
                    println!(
                        "{}: {:p}, {}: {}, {}: {}",
                        l_str[2], &self, l_str[3], type_str, l_str[4], val_str,
                    );
                } else {
                    println!(
                        "{}: {:p}, {}: {}\n{}: {}",
                        l_str[2], &self, l_str[3], type_str, l_str[4], val_str,
                    );
                }
            }
        }
        fn show(&self) {
            self.show_language("zh-cn", false);
        }
        fn show_v(&self) {
            self.show_language("zh-cn", true);
        }
    }
    #[macro_export]
    macro_rules! debug {
        ($e:expr) => {
            $e.show_language("zh-cn", true);
        };
    }
    impl<T: Debug> Tdebug for T {}
}

/// 锁相关
pub mod lock {
    use std::sync::*;

    pub fn silk<T>(t: T) -> Arc<Mutex<T>> {
        // 互斥锁（单读单写锁）
        Arc::new(Mutex::new(t))
    }

    pub fn dblk<T>(t: T) -> RwLock<T> {
        // 读写锁（多度单写锁）
        RwLock::new(t)
    }

    pub fn barr(t: usize) -> Arc<Barrier> {
        // 屏障
        Arc::new(Barrier::new(t))
    }
}
